K-concatenation maximum sum

Time: O(N); Space: O(1); medium

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3

Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5

Output: 2

Example 3:

Input: arr = [-1,-2], k = 7

Output: 0

Constraints:

  • 1 <= len(arr) <= 10^5

  • 1 <= k <= 10^5

  • -10^4 <= arr[i] <= 10^4

Hints:

  1. How to solve the problem for k=1 ?

  2. Use Kadane’s algorithm for k=1.

  3. What are the possible cases for the answer ?

  4. The answer is the maximum between, the answer for k=1, the sum of the whole array multiplied by k, or the maximum suffix sum plus the maximum prefix sum plus (k-2) multiplied by the whole array sum for k > 1.

1. Dynamic programming [O(N), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def kConcatenationMaxSum(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        def max_sub_k_array(arr, k):
            result, curr = float("-inf"), float("-inf")
            for _ in range(k):
                for x in arr:
                    curr = max(curr+x, x)
                    result = max(result, curr)
            return result

        MOD = 10**9+7
        if k == 1:
            return max(max_sub_k_array(arr, 1), 0) % MOD

        return (max(max_sub_k_array(arr, 2), 0) + (k-2)*max(sum(arr), 0)) % MOD

[4]:

s = Solution1()

arr = [1,2]
k = 3
assert s.kConcatenationMaxSum(arr, k) == 9

arr = [1,-2,1]
k = 5
assert s.kConcatenationMaxSum(arr, k) == 2

arr = [-1,-2]
k = 7
assert s.kConcatenationMaxSum(arr, k) == 0